package StackOrQueue;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 描述
 * 给定一个字符串数组，再给定整数 k ，请返回出现次数前k名的字符串和对应的次数。
 * 返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。
 * 对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。
 * 比如"ah1x"小于"ahb"，"231"<”32“
 * 字符仅包含数字和字母
 *
 * */
class NC97 {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    public String[][] topKstrings (String[] strings, int k) {
        String[][] res = new String[k][2];
        //记录字符出现次数
        HashMap<String,Integer> map = new HashMap<>();
        for(int i = 0; i < strings.length; i++){
            if(map.containsKey(strings[i])){
                map.put(strings[i], map.get(strings[i]) + 1);
            }else{
                map.put(strings[i], 1);
            }
        }
        //建立小根堆，自定义比较器(次数值value相同，比较key的字典序，不相同直接比较次数值value)
        PriorityQueue<Map.Entry<String,Integer>> pq =
                new PriorityQueue<>((o1,o2) ->
                        o1.getValue().equals(o2.getValue())
                                ? o2.getKey().compareTo(o1.getKey()) : o1.getValue()-o2.getValue());
        int size = 0;
        //维护size为k的小根堆
        for(Map.Entry<String,Integer> m : map.entrySet()){
            if(size < k){
                pq.offer(m);
                size++;
            }
            //大于堆顶元素插入
            else if((m.getValue().equals(pq.peek().getValue()) ? pq.peek().getKey().compareTo(m.getKey()) : m.getValue() - pq.peek().getValue()) > 0){
                pq.poll();
                pq.offer(m);
            }
        }
        //取出堆中元素，从后向前放置
        for(int i = k - 1; i >= 0; i--){
            Map.Entry entry = pq.poll();
            res[i][0] = (String) entry.getKey();
            res[i][1] = String.valueOf(entry.getValue());
        }
        return res;
    }
}
